A fundamental problem in the field of data storage and communication is the development of practical decoding methods for error-correcting codes (ECC), see Blahut, “Algebraic Codes for Data Transmission,” Cambridge University Press: Cambridge, 2003, and MacWilliams et al., “The Theory of Error-Correcting Codes,” North-Holland: New York, N.Y., 1977.
BINARY LINEAR BLOCK ERROR-CORRECTING CODES
Any references to “codes” herein specifically mean binary linear block error-correcting codes. The basic idea behind these codes is to encode messages of k information bits using blocks of N bits, where N>k. The additional N−k bits are used to decode and correct corrupted messages. A block of N bits is also sometimes called a code-word, or simply a “word.”
Corruption can be caused by failure in the storage media or noise in the transmission channel. Herein, it is assumed that the transmission channel can be modeled as a binary symmetric channel (BSC). In a binary symmetric channel, each bit can be independently flipped with some probability p.
A code C is defined by set of 2k possible blocks of “code-words” having a block length N. k is sometimes called the “dimension” of the code. The “rate” R of a code is defined by R=k/N. Codes are normally much more effective when N and k are large. However, as the size of the parameters N and k increases, so does the difficulty of decoding corrupted messages.
The Hamming distance between two words is defined as the number of bits that differ in the two words. The distance d of a code is defined as the minimum Hamming distance between all pairs of code-words in the code. Codes with a larger value of d have a greater error-correcting capability. Codes with parameters N and k are referred to as (N, k) codes. If the distance d is also known, then they are referred to as (N, k, d) codes.
The class of binary linear block error-correcting codes includes a great variety of sub-classes of codes. Some of the most notable of these sub-classes are the low-density parity check (LDPC) codes; Bose, Chaudhuri, and Hocquenghen (BCH) codes; and codes based on finite geometries, such as Reed-Muller codes.
Reed-Muller Codes and Other Codes Based on Finite Geometries
One important class of error-correcting codes are the Reed-Muller codes, described by Reed et al., in “A Class of Multiple-Error-Correcting Codes and the Decoding Scheme,” IRE Trans. Inform. Theory, vol. 4, pp. 38–49, September 1954, and Muller, “Application of Boolean Algebra to Switching Circuit Design to Error Detection,” IRE Trans. Electron. Comput., vol 3, pp. 6–12, January 1954.
Other multiple-error correcting codes based on finite geometries, herein “finite geometry codes,” were developed in the 1960's and 1970's, for an overview, see chapter 8 of Lin et al., “Error Control Coding: Fundamentals and Applications,” Prentice Hall: Englewood Cliffs, N.J., 1983.
Finite geometry codes can be considered generalizations of Reed-Muller codes. The class of Reed-Muller codes is a sub-set of the class of Euclidean Geometry codes, which is a sub-set of a class of finite geometry codes.
It is possible to determine the parameters N, k, and d of finite geometry codes. The distances of such codes are somewhat worse than the distances of comparable Bose, Chaudhuri, and Hocquenghen (BCH) codes. See any of the textbooks on error-correcting codes previously mentioned for a description of BCH codes. On the other hand, a relative advantage of finite geometry codes is that their decoders are much simpler to implement than decoders for BCH codes.
Majority-Logic, Bounded-Distance, and Maximum-Likelihood Decoders
Up to now, Reed-Muller codes and other finite geometry codes have generally been decoded by a decoding method known as “majority-logic decoding.” Majority-logic decoding is simple to implement and is extremely fast. For a description of majority-logic decoding, see chapter 13 of Blahut, “Algebraic Codes for Data Transmission,” Cambridge University Press: Cambridge, 2003.
A majority-logic decoder is an example of a “bounded-distance decoder.” The standard prior-art decoders for BCH codes, which are based on algebraic methods are also bounded-distance decoders.
A bounded-distance decoder decodes any received word to a nearest code-word, so long as the received word has a Hamming distance to the nearest code-word that is less than or equal to the bounded distance decoding radius t, where t=└(d−1)/2┘. Here, the floor function └x┘ indicates that the fractional part of x is subtracted. There can be at most one code-word within distance t or less of a word. Therefore, a bounded-distance decoder successfully decodes the received word to the transmitted code-word when the channel introduces t or fewer bit flips. Conversely, a bounded-distance decoder fails to decode when the received word has a distance from any code-word that is greater than the decoding radius t. If the channel introduces t or more bit flips, then the bounded-distance decoder fails to correctly decode the transmitted code-word.
The error-correcting performance of a bounded-distance decoder is normally much worse than the performance of an optimal, “maximum-likelihood” decoder. A maximum-likelihood decoder decodes any received word to the nearest code-word, whatever the Hamming distance from the received word to the nearest code-word. Unfortunately, the complexity of true maximum-likelihood decoders increases exponentially with the number of information bits k, making them impractical for codes with a reasonably large number of information bits.
It is desired to provide a practical decoder, which, while not quite optimal, performs much better than a bounded-distance decoder. Such a decoder should be capable of decoding correctly many, if not all, received words that are at a distance greater than t from any code-word.
It is an object of the invention to provide such a decoder for Reed-Muller and other codes based on finite geometries. Such a decoder should greatly-outperform the prior-art majority-logic decoding method.
Bit-Flipping Decoders
Bit-flipping decoders have been described for low-density parity check (LDPC) codes, see Gallager, “Low Density Parity Check Codes,” MIT Press, 1963. As originally described by Gallager, those decoders represent the LDPC code by a parity check matrix. Such a decoder stores a current state of a received word to be decoded as a list of elements. Each element represents one bit of the received word. Each element can take on a value of 0 or 1. The list of elements is initialized to match the bits received after passing through a channel. At each iteration in the Gallager bit-flipping decoding method, every element in the list is tested to see whether it should be flipped. An element is flipped if a sufficient number of parity checks including that bit indicate that the element has the wrong value. The decoder is continually iterated, with the elements flips decided based on the latest updated values of the other elements. When the bit flipping procedure terminates, the values of the elements are taken as the bit values of the decoded word.
Similar tri-state bit flipping decoding methods were described in the context of decoding LDPC codes by Richardson et al., “The Capacity of Low-Density Parity-Check Codes Under Message-Passing Decoding,” IEEE Trans. Information Theory, vol. 47, num. 2, pp. 599–619, February 2001, and by Mitzenmacher “A Note on Low Density Parity Check Codes for Erasures and Errors,” SRC Technical Note 1998-017, December 1998. In a tri-state bit flipping decoder, the elements of the word being decoded can have values of 0, 1, or ?, where the “?” value indicates that the exact state of the element is uncertain.
It is desired to use a bit-flipping decoding method to decode a completely different class of codes, namely codes based on finite geometries, rather than LDPC codes.
Bit-flipping decoders for LDPC codes are not bounded-distance decoders. In contrast to codes based on finite geometries, it is normally impractical to even compute the distance d, for a given LDPC code. The fact that bit-flipping decoders are not bounded-distance decoders means that there is no guarantee that is possible to decode a received word even if it is only corrupted by t or fewer bit flips.
On the other hand, bit-flipping decoders have the advantage of potentially being able to decode-words that are corrupted by more than t bit flips. Bit-flipping decoders have, up to now, not been used for binary block codes other than LDPC codes. The primary reason is that up to now, bit-flipping decoders have been thought to be inappropriate for anything but LDPC codes.
Although Reed-Muller codes date from 1954, and bit-flipping decoders for LDPC codes date from the early 1960's, nobody has previously devised a way to use a bit-flipping decoder for Reed-Muller codes or other finite geometry codes. A possible explanation for this fact is that finite geometry codes must be represented in a non-obvious way for bit-flipping decoders to perform well.
Parity Check Matrix Representations of Codes
A binary block code is “linear” when the modulo 2 sum of any two code-words is also is a code-word. For example, the modulo 2 sum of 1110100 and 0111010 is 1001110. A parity check matrix can represent a linear code. In fact, many different parity check matrices can represent a linear code.
The parity check matrix representing an (N, k) code is defined by a matrix of 1's and 0's, with M rows and N columns. The N columns of the parity check matrix correspond to the N bits of the code.
Each row of the parity check matrix represents a parity check constraint. The bits involved in the constraint represented by a particular row correspond to the columns that have a 1 in that row. The parity check constraint forces the sum of the bits to be even, or equivalently 0 when summed modulo 2. For example, the parity check matrix
                    [                                            1                                      1                                      1                                      0                                      1                                      0                                      0                                                          0                                      1                                      1                                      1                                      0                                      1                                      0                                                          0                                      0                                      1                                      1                                      1                                      0                                      1                                      ]                            (        1        )            represents three constraintsx1⊕x2⊕x3⊕x5=0  (2)x2⊕x3⊕x4⊕x6=0  (3)x3⊕x4⊕x5⊕x7=0,  (4)
where the element xi represents the value of the ith bit, which can be 0 or 1, and the symbol ⊕ represents the modulo 2 sum. This parity check matrix is one resent the well-known Hamming (N=7, k=4, d=3) code.
Some of the M different constraints represented by the parity check matrix are linearly dependent. In the parity check matrix given in equation (1), all the constraints are linearly independent. Another representation for the same code is the parity check matrix
                              [                                                    1                                            1                                            1                                            0                                            1                                            0                                            0                                                                    0                                            1                                            1                                            1                                            0                                            1                                            0                                                                    0                                            0                                            1                                            1                                            1                                            0                                            1                                                                    1                                            0                                            0                                            1                                            1                                            1                                            0                                                                    0                                            1                                            0                                            0                                            1                                            1                                            1                                                                    1                                            0                                            1                                            0                                            0                                            1                                            1                                                                    1                                            1                                            0                                            1                                            0                                            0                                            1                                              ]                .                            (        5        )            
In this parity matrix, the last four rows are obtained by adding together combinations of the first three rows. This means that the last four rows are merely redundant constraints, and there are actually only three linearly independent rows. For example, the fourth row can be obtained by adding together the first two rows.
The number of linearly independent rows of a matrix is sometimes called the “rank” of the matrix. Therefore, this matrix has a rank of three. In general, the rank of an M by N parity check matrix representation of an (N, k) code is N−k.
Finite Geometries
Like other binary linear block codes, finite geometry codes can be represented by a parity check matrix. Of special interest are codes based on finite geometries known as “Euclidean geometries.” Other codes are based on finite geometries known as “projective geometries.” Although some details are different, the principles are the same. For more details see chapter 8 of Lin et al., “Error Control Coding: Fundamentals and Applications,” Prentice Hall: Englewood Cliffs, N.J., 1983.
A finite geometry is a mathematical construct containing a finite number of objects that are analogous to the points, lines, planes, and hyper-planes of ordinary geometry. A finite geometry has a finite number of points called “0-flats.” Certain sets of those points are called “lines,” or “1-flats.” Other sets of lines are called “planes,” or “2-flats.” Sets of planes are called “3-flats,” and sets of 3-flats are called “4-flats,” and so on. In general, the sets are called “μ-flats.” These are well-known definitions in the finite geometry literature.
A Euclidean geometry EG(m, q) is characterized by two parameters, m and q. The “points” or “0-flats” in EG(m, q) are vectors of m different q-ary elements. For example if q=2 and m=3, then the points of EG(m=3, q=2) are vectors consisting of three bits. Thus the eight points of EG(m=3, q=2) are 000, 001, 010, 011, 100, 101, 110, and 111.
The points of EG(m, q) can be labeled a number of different ways. In the example of EG(m=3, q=2), one natural labeling is 000=0, 001=1, 010=2, 011=3, 100=4, 101=5, 110=6, 111=7.
The q-ary elements are to be added or multiplied together according to the rules of a Galois field GF(q). See any textbook on error-correcting codes, including the ones previously referenced, for a description of Galois fields. When q=2, the rules of the Galois field are particularly simple. For GF(q=2), the addition rules are 0+0=0, 0+1=1+0=1, and 1+1=0, and are 0*0=0*1=1*0=0, and 1*1=1.
Lines in a finite Euclidean geometry are defined much as a line is defined in an ordinary geometry. A line in EG(m, q) is a set of points {a0+βa1}, where a0 and a1 are different points in EG(m, q), β runs over all the q-ary elements except 0, and addition and multiplication are defined using the arithmetic rules of GF(q). As an example, for the Euclidean geometry EG(m=3, q=2), it can be seen see that if a0=010, and a1=111, then the corresponding line is {010, 101}. Every pair of points forms a line in the Euclidean geometry EG(m=3, q=2).
Higher order μ-flats are defined in a similar way. For example, planes (2-flats) are defined as sets of points {a0+β1a1+β2a2}, where a0, a1, and a2 are linearly independent points in EG(m,q), and β1 and β2 run over all the non-zero q-ary elements. For example, if a0=001, a1=010, and a1=100, then the corresponding plane is {001, 011, 101, 111}. Using the labeling of points that were selected previously for EG(m=3, q=2), this plane has points {1,3,5,7}.
When defining codes based on Euclidean geometries, the focus is on all the μ-flats that do not include the all-zero point. In the example using EG(m=3,q=2}, the all-zero point is 000=0, and the planes that do not include the all-zero point are {1,2,4,7}, {1,2,5,6}, {1,3,4,6}, {1,3,5,7}, {2,3,4,5}, {2,3,6,7}, and {4,5,6,7}, where the labels are as defined for the points.
For a collection of n objects in total, and a set of those objects, one can define an “incidence vector” of the set with respect to the objects, which is a vector of n 0's and 1's, where a 1 in position i indicates that that the ith object is in the set. For example, if there are seven objects with labels 1 to 7, and one considers the set {2,5,6}, then the incidence vector for the set {1,2,5,6} with respect to the numbers 1 through 7 is 1100110.
In the example using EG(m=3, q=2), if the n objects are the 7 non-zero points, then the incidence vectors for the planes that do not contain the all-zeros point with respect to the non-zero points are 1101001, 1100110, 1011010, 1010101, 0111100, 0110011, and 0001111.
Codes Based on Finite Geometries
A Euclidean Geometry EG(m,s,v) code can be defined by a parity check matrix whose rows are the incidence vectors of all (v+1)-flats in EG(m,2s) that do not contain the all-zeros point with respect to the non-zero point. For example, the EG(m=3,s=1, v=1) code can be defined by the parity check matrix
      [                            1                          1                          0                          1                          0                          0                          1                                      1                          1                          0                          0                          1                          1                          0                                      1                          0                          1                          1                          0                          1                          0                                      1                          0                          1                          0                          1                          0                          1                                      0                          1                          1                          1                          1                          0                          0                                      0                          1                          1                          0                          0                          1                          1                                      0                          0                          0                          1                          1                          1                          1                      ]    .
It is important to note that the parity check matrix for a Euclidean geometry code defined in this way contains redundant rows. For example, although there are 7 rows in the parity check matrix for the EG(m=3, s=1, v=1) code above, only 3 of the rows are linearly independent, and the code is actually equivalent to the (n=7, k=4, d=3) Hamming code that was used previously as an example.
With an appropriate re-labeling of the points, a code based on a Euclidean Geometry can be defined in a cyclic form. For example, if the labeling 010=1, 100=2, 011=3, 001=4, 101=5, 110=6, 111=7 is used, then the parity check matrix is defined as
      [                            1                          1                          1                          0                          1                          0                          0                                      0                          1                          1                          1                          0                          1                          0                                      0                          0                          1                          1                          1                          0                          1                                      1                          0                          0                          1                          1                          1                          0                                      0                          1                          0                          0                          1                          1                          1                                      1                          0                          1                          0                          0                          1                          1                                      1                          1                          0                          1                          0                          0                          1                      ]     that has a circulant form making the cyclic symmetry more obvious.
As mentioned previously, Reed-Muller codes can be considered a special case of a code based on a Euclidean geometry. To be more precise, Reed-Muller codes are Euclidean geometry codes with s=1.
Codes based on other finite geometries are defined in a similar way. One uses the incidence vectors of high-order μ-flats with respect to the points of the finite geometry to define a parity check matrix for the code.
As described above, the most commonly used prior art decoders for finite geometry codes are majority-logic decoders, which are bounded-distance decoders.
It is desired to provide a practical decoding method which out-performs majority-logic decoders for finite geometry codes.